package niuke;

/**
 * description:
 * author:张腾
 * date:2021-06-27
 */

/**
 * 给定一个整型数组 arrarr 和一个整数 k(k>1)k(k>1)。
 * 已知 arrarr 中只有 1 个数出现一次，其他的数都出现 kk 次。
 * 请返回只出现了 1 次的数。
 */
//通过计算数组中每个数字二进制各位的和，如果计算出来的和是k的倍数说明没有出现k次的那个数这一位是0
public class NC156 {
    public int foundOnceNumber (int[] arr, int k) {
        // write code here
        int[] binarySum = new int[32];
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (int num : arr) {
                //右移
                sum += (num>>i)&1;
            }
            binarySum[i] = sum;
        }
        int res = 0;
        for (int i = 0; i < 32; i++) {
            //左移
            if (binarySum[i]%k!=0) res += 1<<i;
        }
        return res;
    }
}
